# Average Case

• 2026년 6월 27일 알고리즘
  quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가

  quick sort는 pivot으로 배열을 가르는 분할 정복이다. 두 포인터 분할 과정을 보고 최선 O(n log n)과 최악 O(n²)이 갈리는 지점을 짚는다. 핵심은 평균 분석이다. 기댓값 점화식 E(n)을 세워 평균이 Θ(n log n)임을 유도한다.